{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Nesting Depth of the Parentheses"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxDepth"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #括号的最大嵌套深度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>如果字符串满足以下条件之一，则可以称之为 <strong>有效括号字符串</strong><strong>（valid parentheses string</strong>，可以简写为 <strong>VPS</strong>）：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>字符串是一个空字符串 <code>\"\"</code>，或者是一个不为 <code>\"(\"</code> 或 <code>\")\"</code> 的单字符。</li>\n",
    "\t<li>字符串可以写为 <code>AB</code>（<code>A</code> 与 <code>B</code>&nbsp;字符串连接），其中 <code>A</code> 和 <code>B</code> 都是 <strong>有效括号字符串</strong> 。</li>\n",
    "\t<li>字符串可以写为 <code>(A)</code>，其中 <code>A</code> 是一个 <strong>有效括号字符串</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>类似地，可以定义任何有效括号字符串&nbsp;<code>S</code> 的 <strong>嵌套深度</strong> <code>depth(S)</code>：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>depth(\"\") = 0</code></li>\n",
    "\t<li><code>depth(C) = 0</code>，其中 <code>C</code> 是单个字符的字符串，且该字符不是 <code>\"(\"</code> 或者 <code>\")\"</code></li>\n",
    "\t<li><code>depth(A + B) = max(depth(A), depth(B))</code>，其中 <code>A</code> 和 <code>B</code> 都是 <strong>有效括号字符串</strong></li>\n",
    "\t<li><code>depth(\"(\" + A + \")\") = 1 + depth(A)</code>，其中 <code>A</code> 是一个 <strong>有效括号字符串</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>例如：<code>\"\"</code>、<code>\"()()\"</code>、<code>\"()(()())\"</code> 都是 <strong>有效括号字符串</strong>（嵌套深度分别为 0、1、2），而 <code>\")(\"</code> 、<code>\"(()\"</code> 都不是 <strong>有效括号字符串</strong> 。</p>\n",
    "\n",
    "<p>给你一个 <strong>有效括号字符串</strong> <code>s</code>，返回该字符串的<em> </em><code>s</code> <strong>嵌套深度</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"(1+(2*3)+((<strong>8</strong>)/4))+1\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>数字 8 在嵌套的 3 层括号中。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"(1)+((2))+(((<strong>3</strong>)))\"\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 100</code></li>\n",
    "\t<li><code>s</code> 由数字 <code>0-9</code> 和字符 <code>'+'</code>、<code>'-'</code>、<code>'*'</code>、<code>'/'</code>、<code>'('</code>、<code>')'</code> 组成</li>\n",
    "\t<li>题目数据保证括号表达式 <code>s</code> 是 <strong>有效的括号表达式</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-nesting-depth-of-the-parentheses](https://leetcode.cn/problems/maximum-nesting-depth-of-the-parentheses/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-nesting-depth-of-the-parentheses](https://leetcode.cn/problems/maximum-nesting-depth-of-the-parentheses/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"(1+(2*3)+((8)/4))+1\"', '\"(1)+((2))+(((3)))\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        return max(self.maxDepth(root.left)+1, self.maxDepth(root.right) + 1)\n",
    "       \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return 0\n",
    "\n",
    "        stack = [root]\n",
    "        depth =1\n",
    "\n",
    "        while len(stack)>0:\n",
    "            p = stack[-1]\n",
    "            if p.left is not None:\n",
    "                stack.append(p.left)\n",
    "                depth = max(len(stack), depth)\n",
    "                p.left = None\n",
    "\n",
    "            elif p.right is not None:\n",
    "                stack.append(p.right)\n",
    "                depth = max(len(stack), depth)\n",
    "                p.right = None\n",
    "\n",
    "            else:\n",
    "                stack.pop()\n",
    "\n",
    "        return depth\n",
    "\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        a = []\n",
    "        b = TreeNode(0)\n",
    "        max = 0\n",
    "        if root == None:\n",
    "            return 0\n",
    "        a.append(root)\n",
    "        while a!=[]:\n",
    "            if a[-1].left:\n",
    "                b = a[-1].left\n",
    "                a[-1].left = None\n",
    "                a.append(b)             \n",
    "            elif a[-1].right:\n",
    "                b = a[-1].right\n",
    "                a[-1].right = None\n",
    "                a.append(b)\n",
    "            else:\n",
    "                if len(a)>max:\n",
    "                    max = len(a)\n",
    "                a.pop()\n",
    "        return max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return 0\n",
    "        stack=[(root,1)]\n",
    "        dictmap={}\n",
    "        while stack:\n",
    "            root,depth=stack.pop()\n",
    "            if root.val in dictmap:\n",
    "                if dictmap[root.val]<depth:\n",
    "                    dictmap[root.val]=depth\n",
    "            else:\n",
    "                dictmap[root.val]=depth\n",
    "            if root.right:\n",
    "                stack.append((root.right,depth+1))\n",
    "            if root.left:\n",
    "                stack.append((root.left,depth+1))\n",
    "        print(dictmap)\n",
    "        return max(dictmap.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        query=[]\n",
    "        res=[]\n",
    "        query.append(root)\n",
    "        if root:\n",
    "            res.append(root.val)\n",
    "        else:\n",
    "            return 0\n",
    "        while query:\n",
    "            temp=query.pop(0)\n",
    "            left=temp.left\n",
    "            right=temp.right\n",
    "            if left:\n",
    "                query.append(left)\n",
    "                res.append(left.val)\n",
    "            else:\n",
    "                res.append(left)\n",
    "            if right:\n",
    "                query.append(right)\n",
    "                res.append(right.val)\n",
    "            else:\n",
    "                res.append(right)\n",
    "                \n",
    "        sign=[0,1]\n",
    "        j=0\n",
    "        while True:\n",
    "            m=0\n",
    "            for k in res[sign[j]:sign[j+1]]:\n",
    "                if k!=None:\n",
    "                    m+=1\n",
    "            j+=1\n",
    "            sign.append(sign[-1]+2*m)\n",
    "            if len(res)<=sign[-1]:\n",
    "                break\n",
    "        # sign.pop(0)\n",
    "        print('sign:',sign)\n",
    "        \n",
    "        i=0\n",
    "        s=0\n",
    "        re=[]\n",
    "        while True:\n",
    "            if len(res)>sign[i]+1:\n",
    "                re.append(res[sign[i]:sign[i+1]])\n",
    "                # print(sign[i])\n",
    "            else:\n",
    "                break\n",
    "            # s+=2**i\n",
    "            i+=1\n",
    "        \n",
    "        result=[]\n",
    "        for num in re:\n",
    "            result.append([])\n",
    "            for i in range(len(num)):\n",
    "                if num[i]!=None:\n",
    "                    result[-1].append(num[i])   \n",
    "        return len(result)-1\n",
    "        print(res)\n",
    "        print(re)\n",
    "        print(result)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "      \"\"\"\n",
    "      :type root: TreeNode\n",
    "      :rtype: int\n",
    "      \"\"\"\n",
    "      if root is None:\n",
    "        return 0\n",
    "      nodes = [root]\n",
    "      max_depth = 1\n",
    "      node_to_depth = {root: 1}\n",
    "      while nodes:\n",
    "          node = nodes.pop(0)\n",
    "          depth = node_to_depth[node]\n",
    "          left = node.left\n",
    "          right = node.right\n",
    "          depth += 1\n",
    "          if left:\n",
    "              max_depth = max(max_depth, depth)\n",
    "              node_to_depth[left] = depth\n",
    "              nodes.append(left)\n",
    "          if right:\n",
    "              max_depth = max(max_depth, depth)\n",
    "              node_to_depth[right] = depth\n",
    "              nodes.append(right)\n",
    "      return max_depth\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        if root is not None:\n",
    "            stack.append((1,root))\n",
    "            depth = 0\n",
    "            while stack != []:\n",
    "                current_depth, root = stack.pop()\n",
    "                if root:\n",
    "                    depth = max(depth, current_depth)\n",
    "                    stack.append((current_depth + 1, root.right))\n",
    "                    stack.append((current_depth + 1, root.left))\n",
    "            return depth\n",
    "        else:\n",
    "            return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return 0\n",
    "        def dfs(root):\n",
    "            if root != None:\n",
    "                return max(dfs(root.left),dfs(root.right))+1\n",
    "                \n",
    "                \n",
    "            else:\n",
    "                return 0\n",
    "            \n",
    "            \n",
    "        \n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        depths = []\n",
    "        def explore(root,height,l):\n",
    "            if not root.left and not root.right:\n",
    "                l.append(height)\n",
    "                return \n",
    "            \n",
    "            if root.left:\n",
    "                explore(root.left,height+1,l)\n",
    "            \n",
    "            if root.right:\n",
    "                explore(root.right,height+1,l)\n",
    "                \n",
    "        explore(root,1,depths)\n",
    "        \n",
    "        return max(depths)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def levelTree(root, last_level):\n",
    "            if not root:\n",
    "                return last_level\n",
    "            l = last_level + 1\n",
    "            r = last_level + 1\n",
    "            if root.left:\n",
    "                l = levelTree(root.left, last_level + 1)\n",
    "            if root.right:\n",
    "                r = levelTree(root.right, last_level + 1)\n",
    "            return max(l, r)\n",
    "\n",
    "        return levelTree(root, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        \n",
    "        def height(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = height(node.left)\n",
    "            right =height(node.right)\n",
    "            return max(left,right)+1\n",
    "        \n",
    "        return height(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        return 1 + max(map(self.maxDepth,(root.left,root.right)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        def dfs(root):\n",
    "            if root == None:\n",
    "                return 0\n",
    "            else:\n",
    "                print(root.val)\n",
    "                l = dfs(root.left) + 1\n",
    "                r = dfs(root.right) + 1 \n",
    "                return max(l, r)\n",
    "        \n",
    "    \n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return 1+max(map(self.maxDepth,(root.left,root.right))) if root else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        count = 0\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            count += 1\n",
    "            tempstack = []  # 装下一层节点\n",
    "            for root in stack:\n",
    "                if root.left:\n",
    "                    tempstack.append(root.left)\n",
    "                if root.right:\n",
    "                    tempstack.append(root.right)\n",
    "            stack = tempstack\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        stack = []\n",
    "        if root is not None:\n",
    "            stack.append(root)\n",
    "        \n",
    "        depth = 0\n",
    "        while stack != []:\n",
    "\n",
    "            depth += 1\n",
    "            for i in range(len(stack)):\n",
    "                root = stack.pop(0)\n",
    "                if root.left != None:\n",
    "                    stack.append(root.left)\n",
    "                if root.right != None:\n",
    "                    stack.append(root.right)\n",
    "        \n",
    "        return depth\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    # sol 1: Recursion\n",
    "    def maxDepth_v1(self, root: TreeNode) -> int:\n",
    "        def helper(root: TreeNode, level: int) -> int:\n",
    "            if not root:\n",
    "                return level - 1\n",
    "            \n",
    "            return max(helper(root.left, level + 1), helper(root.right, level + 1))\n",
    "        \n",
    "        return helper(root, 1)\n",
    "\n",
    "    \n",
    "    # sol 2: Level-order-travesarl.\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        from collections import deque\n",
    "        if not root:\n",
    "            return 0\n",
    "        q = deque([root])\n",
    "        level = 0\n",
    "        while q:\n",
    "            level += 1\n",
    "            prev_level_size = len(q)\n",
    "            for _ in range(prev_level_size):\n",
    "                node = q.popleft()\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "        \n",
    "        return level"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            ans+=1\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        depth = 0\n",
    "        stack = []\n",
    "        stack.append(root)\n",
    "\n",
    "        while stack:\n",
    "            length = len(stack)\n",
    "            for _ in range(length):\n",
    "                root = stack.pop(0)\n",
    "                if root.left:\n",
    "                    stack.append(root.left)\n",
    "                if root.right:\n",
    "                    stack.append(root.right)\n",
    "\n",
    "            depth += 1\n",
    "\n",
    "        return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        depth = 0\n",
    "        node = root\n",
    "        my_queue = []\n",
    "        my_queue.append(node)\n",
    "\n",
    "        while my_queue:\n",
    "            count = len(my_queue)\n",
    "            depth = depth + 1\n",
    "            while count > 0:\n",
    "                node = my_queue.pop(0)\n",
    "                if node.left is not None:\n",
    "                    my_queue.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    my_queue.append(node.right)\n",
    "                count -= 1\n",
    "\n",
    "        return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        nodes = [root]\n",
    "        res = []\n",
    "        while len(nodes) > 0:\n",
    "            n = len(nodes)\n",
    "            for node in nodes[:]:\n",
    "                if node.left:\n",
    "                    nodes.append(node.left)\n",
    "                if node.right:\n",
    "                    nodes.append(node.right)\n",
    "            p, nodes = nodes[:n], nodes[n:]\n",
    "            res.append([i.val for i in p])\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        '''递归，后序遍历（DFS）\n",
    "        if not root:\n",
    "            return 0\n",
    "        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1\n",
    "        '''\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        queue,res=[root],0\n",
    "        while queue:\n",
    "            tem = []\n",
    "            for i in queue:\n",
    "                if i.left:\n",
    "                    tem.append(i.left)\n",
    "                if i.right:\n",
    "                    tem.append(i.right)\n",
    "            queue = tem \n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        if not root.left and not root.right:\n",
    "            return 1\n",
    "\n",
    "        l = self.maxDepth(root.left)\n",
    "        r = self.maxDepth(root.right)\n",
    "\n",
    "        return max(l, r) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        depth_v = 0\n",
    "        if root is None:\n",
    "            return depth_v\n",
    "        node_list = [root]\n",
    "        while(True):\n",
    "            if len(node_list) == 0:\n",
    "                return depth_v\n",
    "            depth_v += 1\n",
    "            new_node_list = []\n",
    "            for item in node_list:\n",
    "                if item.left is not None:\n",
    "                    new_node_list.append(item.left)\n",
    "                if item.right is not None:\n",
    "                    new_node_list.append(item.right)\n",
    "            node_list = new_node_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root :\n",
    "            return 0\n",
    "        queue = deque([root])\n",
    "        height = 0\n",
    "        while queue:\n",
    "            currentsize=len(queue)\n",
    "            for i in range(currentsize):\n",
    "                node=queue.popleft()\n",
    "                if node.left!=None:\n",
    "                    queue.append(node.left)\n",
    "                if node.right!=None:\n",
    "                    queue.append(node.right)\n",
    "            height+=1\n",
    "        return height"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        queue = collections.deque([root])\n",
    "        depth = 0\n",
    "        while queue:\n",
    "            depth += 1\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                # 将不再需要使用的节点从内存中删除\n",
    "                node.left = None\n",
    "                node.right = None\n",
    "        return depth\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "\n",
    "        queue_ = [root]\n",
    "        depth = 0\n",
    "        while queue_:\n",
    "            length = len(queue_)\n",
    "            for i in range(length):\n",
    "                cur = queue_.pop(0)\n",
    "                #子节点入队列\n",
    "                if cur.left: queue_.append(cur.left)\n",
    "                if cur.right: queue_.append(cur.right)\n",
    "            depth += 1\n",
    "\n",
    "        return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        deep = 0\n",
    "        if root==None:\n",
    "            return deep\n",
    "        from collections import deque\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            deep +=1\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                cur = queue.popleft()\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "        return deep\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        res=0\n",
    "        stack=[[root,1]]\n",
    "        while stack:\n",
    "            node,depth=stack.pop()\n",
    "            if node:\n",
    "                res=max(res,depth)\n",
    "                stack.append([node.left,depth+1])\n",
    "                stack.append([node.right,depth+1])\n",
    "        return res\n",
    "       \n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        queue = collections.deque([root])\n",
    "        distance = {root: 1}\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "                distance[node.left] = distance[node] + 1\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "                distance[node.right] = distance[node] + 1\n",
    "        return  distance[max(distance, key=distance.get)]    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        result = []\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            vals = []\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                vals.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            result.append(vals)\n",
    "        return len(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        # DFS\n",
    "        # if root:\n",
    "        #     return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))\n",
    "        # else:\n",
    "        #     return 0\n",
    "\n",
    "        # BFS\n",
    "        # queue = collections.deque()\n",
    "        # if root: \n",
    "        #     queue.append(root)\n",
    "        # depth = 0\n",
    "        # while queue:\n",
    "        #     n = len(queue)\n",
    "        #     while n > 0:\n",
    "        #         node = queue.popleft()\n",
    "        #         if node.left:\n",
    "        #             queue.append(node.left)\n",
    "        #         if node.right:\n",
    "        #             queue.append(node.right)\n",
    "        #         n -= 1\n",
    "        #     depth += 1\n",
    "        # return depth\n",
    "\n",
    "        # Stack\n",
    "        maxDepth = 0\n",
    "        if not root: return 0\n",
    "        stk = [(root,1)]\n",
    "        while stk:\n",
    "            node, depth = stk.pop()\n",
    "            maxDepth = max(maxDepth, depth)\n",
    "            if node.left:\n",
    "                stk.append((node.left, depth + 1))\n",
    "            if node.right:\n",
    "                stk.append((node.right, depth + 1))\n",
    "        return maxDepth\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        if not root:\n",
    "            return res\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            level = []\n",
    "            for node in queue:\n",
    "                if node.left:\n",
    "                    level.append(node.left)\n",
    "                if node.right:\n",
    "                    level.append(node.right)\n",
    "            res += 1\n",
    "            queue = level\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        result=[]\n",
    "        queue = collections.deque([root])\n",
    "        \n",
    "        while queue:\n",
    "            level_size = len(queue)\n",
    "            #prev = None\n",
    "            level=[]\n",
    "            for i in range(level_size):\n",
    "                node = queue.popleft()\n",
    "                \n",
    "                # if prev:\n",
    "                #     prev.next = node\n",
    "                \n",
    "                # prev = node\n",
    "                \n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                \n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                level.append(node)\n",
    "            result.append(level)\n",
    "        ans=len(result)\n",
    "        return ans     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 + max(self.maxDepth(root.right), self.maxDepth(root.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        l_depth=self.maxDepth(root.left)\n",
    "        r_depth=self.maxDepth(root.right)\n",
    "        return max(l_depth,r_depth) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        if root is None:\n",
    "            return 0\n",
    "        md = 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))\n",
    "        return md\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        if not root.children:\n",
    "            return 1\n",
    "        \n",
    "        maxd = 0\n",
    "        for child in root.children:\n",
    "            depth = self.maxDepth(child)\n",
    "            if depth > maxd:\n",
    "                maxd = depth\n",
    "        \n",
    "        return 1+maxd\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: Node\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return 0\n",
    "        child_depths = [self.maxDepth(_) for _ in root.children]\n",
    "        return max(child_depths) + 1 if child_depths else 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "def func(root, depth):\n",
    "    if root == None:\n",
    "        return depth\n",
    "    depth += 1\n",
    "    max = 0\n",
    "    for c in root.children:\n",
    "        d = func(c, 0)\n",
    "        if d > max:\n",
    "            max = d\n",
    "    return depth + max\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> 'int':\n",
    "        return func(root, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val, children):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> 'int':\n",
    "        if not root:\n",
    "            return 0\n",
    "        if not root.children:\n",
    "            return 1\n",
    "        return max(self.maxDepth(x) for x in root.children) + 1\n",
    "            \n",
    "            \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        if root is None: \n",
    "            return 0 \n",
    "        elif root.children == []:\n",
    "            return 1\n",
    "        else: \n",
    "            height = [self.maxDepth(c) for c in root.children]\n",
    "            return max(height) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        from collections import deque\n",
    "\n",
    "        if not root:\n",
    "            return 0\n",
    "        cur_que = deque()\n",
    "        cur_que.appendleft(root)\n",
    "        ret_depth = 0\n",
    "        last_layer_len = 1\n",
    "        cur_layer_len = 0\n",
    "\n",
    "        while last_layer_len:\n",
    "            pop_item = cur_que.pop()\n",
    "            for item in pop_item.children:\n",
    "                cur_que.appendleft(item)\n",
    "                cur_layer_len += 1\n",
    "\n",
    "            last_layer_len -= 1\n",
    "            if last_layer_len == 0:\n",
    "                last_layer_len = cur_layer_len\n",
    "                cur_layer_len = 0\n",
    "                ret_depth += 1\n",
    "\n",
    "        return ret_depth\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        stack = []\n",
    "        if root != None:\n",
    "            stack.append((1,root))\n",
    "        depth = 0\n",
    "        while len(stack) > 0:\n",
    "            curDepth, node = stack.pop()\n",
    "            if node != None:\n",
    "                depth = max(depth, curDepth)\n",
    "                for c in node.children:\n",
    "                    stack.append((curDepth+1, c))\n",
    "        return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        stack = [(1, root)]\n",
    "        level = 1\n",
    "        while stack:\n",
    "            curr_level, node = stack.pop()\n",
    "            if node:\n",
    "                level = max(curr_level, level)\n",
    "                for c in node.children:\n",
    "                    stack.append((curr_level+1, c))\n",
    "        return level"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        '\"迭代\"'\n",
    "        queue = []\n",
    "        depth = 0\n",
    "        if root is not None:\n",
    "            queue.append((1, root))\n",
    "        while queue:\n",
    "            current_depth, root = queue.pop()\n",
    "            \n",
    "            if root:\n",
    "                depth = max(depth, current_depth)\n",
    "                for c in root.children:\n",
    "                    queue.append((current_depth+1, c))\n",
    "        return depth\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        def dfs(cur_node):\n",
    "            temp_arr = []\n",
    "            if cur_node.children:\n",
    "                for child in cur_node.children:\n",
    "                    temp_arr.append(dfs(child))\n",
    "                return 1+max(temp_arr)\n",
    "            else:\n",
    "                return 1\n",
    "        \n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        nodes = []\n",
    "        for i in root.children:\n",
    "            if i:\n",
    "                nodes.append(self.maxDepth(i))\n",
    "        if not nodes:\n",
    "            return 1\n",
    "        return max(nodes) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        elif not root.children:\n",
    "            return 1\n",
    "        \n",
    "        else:\n",
    "            depth = [self.maxDepth(c) for c in root.children]\n",
    "        \n",
    "        return max(depth) + 1\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        if not root: return 0\n",
    "        q = collections.deque([root])\n",
    "        res = 0\n",
    "        while q:\n",
    "            size = len(q)\n",
    "            res += 1\n",
    "            for _ in range(size):\n",
    "                node = q.popleft()\n",
    "                q.extend(node.children)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        # dfs\n",
    "        # if not root:\n",
    "        #     return 0\n",
    "        # else:\n",
    "        #     depth = 0\n",
    "        #     level = 0\n",
    "        #     for node in root.children:\n",
    "        #         level = self.maxDepth(node)\n",
    "        #         depth = max(depth, level)\n",
    "        # return depth + 1\n",
    "\n",
    "        # bfs\n",
    "        if not root:\n",
    "            return 0\n",
    "        depth = 0\n",
    "        queue = collections.deque([root])\n",
    "        while queue:\n",
    "            for _ in range(len(queue)):\n",
    "                root = queue.popleft()\n",
    "                queue.extend(root.children)\n",
    "            depth += 1\n",
    "            \n",
    "        return depth\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        depth = 0\n",
    "        for i in range(len(root.children)):\n",
    "            depth = max(depth, self.maxDepth(root.children[i]))\n",
    "        return depth + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        # children 返回的是所有子节点，形式为一个list，可通过遍历处理每个子节点       \n",
    "        if root == None:\n",
    "            return 0\n",
    "        \n",
    "        depth = 0\n",
    "        childs = root.children\n",
    "        for child in childs:\n",
    "            depth = max(depth, self.maxDepth(child))\n",
    "\n",
    "        return depth + 1   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        return max((self.maxDepth(child) for child in root.children), default=0) + 1 if root else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        # if not root:\n",
    "        #     return 0\n",
    "        depth = 0\n",
    "        def traversal(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            depth =max((self.maxDepth(child) for child in root.children), default=0) + 1\n",
    "            return depth\n",
    "        return traversal(root)\n",
    "        # return max((self.maxDepth(child) for child in root.children), default=0) + 1 if root else 0\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        tmp = root.children\n",
    "        count = 1\n",
    "        while(tmp):\n",
    "            n = len(tmp)\n",
    "            for i in range(n):\n",
    "                tmp.extend(tmp.pop(0).children)\n",
    "            count = count + 1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        d =1\n",
    "        for node in root.children:\n",
    "            d=max(d,self.maxDepth(node)+1)\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a Node.\n",
    "class Node:\n",
    "    def __init__(self, val=None, children=None):\n",
    "        self.val = val\n",
    "        self.children = children\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: 'Node') -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        res = 0\n",
    "        q = [root]\n",
    "        while q:\n",
    "            l = len(q)\n",
    "            res += 1\n",
    "            for i in range(l):\n",
    "                tmp = q.pop(0)\n",
    "                for j in tmp.children:\n",
    "                    q.append(j)\n",
    "\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        depth, ans = 0, 0 \n",
    "        for ch in s:\n",
    "            if ch == \"(\":\n",
    "                depth += 1\n",
    "                ans = max(depth, ans)\n",
    "            elif ch == \")\":\n",
    "                depth -= 1\n",
    "        return ans\n",
    "\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        res = 0\n",
    "\n",
    "        curr = 0\n",
    "        for char in s:\n",
    "            if char == '(':\n",
    "                curr += 1\n",
    "            elif char == ')':\n",
    "                curr -= 1\n",
    "            res = max(res, curr)\n",
    "            continue\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "\n",
    "        stack = [] \n",
    "        result = []  # 用来记录每个子VPS的深度\n",
    "        num = 0\n",
    "\n",
    "        for ch in s:   \n",
    "\n",
    "            if ch == '(':\n",
    "                stack.append(ch)\n",
    "                num += 1\n",
    "            elif ch == ')':\n",
    "                stack.pop()\n",
    "                result.append(num)\n",
    "                num -= 1\n",
    "            else:\n",
    "                continue\n",
    "        \n",
    "        return max(result) if result else 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        stack = []\n",
    "        ans = 0\n",
    "        for c in s:\n",
    "            if c == \"(\":\n",
    "                stack.append(c)\n",
    "            elif c == \")\":\n",
    "                ans = max(ans, len(stack))\n",
    "                stack.pop()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        count = 0\n",
    "        max_ = 0\n",
    "        for i in s:\n",
    "            if i == \"(\":\n",
    "                count += 1\n",
    "                if count > max_:\n",
    "                    max_ = count\n",
    "            elif i == \")\":\n",
    "                count -= 1\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        max_ans=0\n",
    "        tmp=0\n",
    "        dic={'(':1,')':-1}\n",
    "        for ch in s:\n",
    "            if ch in dic:\n",
    "                tmp+=dic[ch]\n",
    "                max_ans=max(tmp,max_ans)\n",
    "        return max_ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        l, res = [], 0\n",
    "        for w in s:\n",
    "            if w == '(':\n",
    "                l.append(w)\n",
    "                if len(l)>res:\n",
    "                    res = len(l)\n",
    "            elif w == ')':\n",
    "                l.pop()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        temp_depth = 0\n",
    "        depths = [0]\n",
    "        flag = True\n",
    "        for c in s:\n",
    "            if c==')':\n",
    "                if flag:\n",
    "                    depths.append(temp_depth)\n",
    "                    flag = False\n",
    "                temp_depth -= 1\n",
    "            elif c=='(':\n",
    "                temp_depth += 1\n",
    "                flag = True\n",
    "        return max(depths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans,size=0,0\n",
    "        for ch in s:\n",
    "            if ch=='(':\n",
    "                size+=1\n",
    "                ans=max(ans,size)\n",
    "\n",
    "            elif ch==')':\n",
    "                size-=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        cur=0\n",
    "        res=0\n",
    "        for i in s:\n",
    "            if i==\"(\":\n",
    "                cur+=1\n",
    "                res = max(res,cur)\n",
    "            if i==\")\":\n",
    "                cur-=1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        result=middle=0\n",
    "        for token in s:\n",
    "            if token==\"(\":\n",
    "                middle+=1\n",
    "            elif token==\")\":\n",
    "                middle-=1\n",
    "            result=max(result,middle)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self,s) -> int:\n",
    "        ans,size=0,0\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                size+=1\n",
    "                ans=max(ans,size)\n",
    "            elif i == ')':\n",
    "                size-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        count = 0\n",
    "        res = 0\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                count += 1\n",
    "            elif i == ')':\n",
    "                res = max(res,count)\n",
    "                count -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        left=0\n",
    "        right=0\n",
    "        maxv=0\n",
    "        for i in s:\n",
    "            if i=='(':\n",
    "                left+=1\n",
    "            elif i==')':\n",
    "                right+=1\n",
    "            maxv=max(maxv,left-right)\n",
    "        return maxv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        res = 0\n",
    "        temp_res = 0\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                temp_res += 1\n",
    "            elif i == ')':\n",
    "                if temp_res > res:\n",
    "                    res = temp_res\n",
    "                temp_res -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        vps = []\n",
    "        ret = 0\n",
    "        num =0\n",
    "        for i in s:\n",
    "            if i == \"(\":\n",
    "               # num = 0\n",
    "                vps.append(i)\n",
    "            elif i == \")\":\n",
    "                vps.pop(-1)\n",
    "               # num += 1\n",
    "            if len(vps) > ret:\n",
    "                ret = len(vps)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        l = ans = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                l += 1\n",
    "                ans = max(ans, l)\n",
    "            elif c == ')':\n",
    "                l -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        top = 0\n",
    "        ret = 0\n",
    "        for i in range(0, len(s)):\n",
    "            if s[i] == '(' :\n",
    "                top+=1\n",
    "                if top > ret:\n",
    "                    ret+=1\n",
    "            if s[i] == ')':\n",
    "                top-=1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        stack ,cnt = 0,0\n",
    "        for i in s:\n",
    "            if i=='(':\n",
    "                cnt+=1\n",
    "                stack = max(stack,cnt)\n",
    "            elif i == ')':\n",
    "                cnt-=1\n",
    "        return stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans = cur = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                cur += 1\n",
    "                ans = max(cur, ans)\n",
    "            elif c == ')':\n",
    "                cur -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans = cur = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                cur += 1\n",
    "                ans = max(cur, ans)\n",
    "            elif c == ')':\n",
    "                cur -= 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "   \n",
    "       \n",
    "       \n",
    "                \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        result,size = 0,0\n",
    "        for e in s:\n",
    "            if e == '(':\n",
    "                size += 1\n",
    "                result = max(result, size)\n",
    "            elif e == ')':\n",
    "                size -= 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        res, ans = 0, 0\n",
    "        for ch in s:\n",
    "            if ch == '(':\n",
    "                res += 1\n",
    "                ans = max(ans, res)\n",
    "            elif ch == ')':\n",
    "                res -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        stack = []\n",
    "        num = 0\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                stack.append(i)\n",
    "            elif i == ')':\n",
    "                num = max(num, len(stack))\n",
    "                stack.pop()\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        maxDep = 0\n",
    "        dep = 0\n",
    "        for char in s:\n",
    "            if char == '(':\n",
    "                dep += 1\n",
    "                maxDep = max(maxDep, dep)\n",
    "            if char == ')':\n",
    "                dep -= 1\n",
    "        return maxDep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans, size = 0, 0\n",
    "        for ch in s:\n",
    "            if ch == '(':\n",
    "                size += 1\n",
    "                ans = max(ans, size)\n",
    "            elif ch == \")\":\n",
    "                size -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        sums = 0\n",
    "        for ch in s:\n",
    "            if ch == '(':\n",
    "                sums += 1\n",
    "                ans = max(sums, ans)\n",
    "            elif ch == ')':\n",
    "                sums -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans = cur = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                cur += 1\n",
    "                ans = max(cur, ans)\n",
    "            elif c == ')':\n",
    "                cur -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        maxd = 0\n",
    "        deepth = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                deepth += 1\n",
    "            if s[i] == ')':\n",
    "                deepth -= 1\n",
    "            maxd = max(maxd, deepth)\n",
    "        return maxd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        heap = []\n",
    "        depth = 0\n",
    "        for i in range(len(s)):\n",
    "            char = s[i]\n",
    "            if char == '(':\n",
    "                heap.append(')')\n",
    "                depth = max(len(heap), depth)\n",
    "            elif char == ')':\n",
    "                heap.remove(heap[-1])\n",
    "        return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "      ans,cur=0,0\n",
    "      for c in s:\n",
    "          if c=='(':\n",
    "              cur+=1\n",
    "              ans = max(cur,ans)\n",
    "          elif c==')':\n",
    "              cur-=1\n",
    "      return ans             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        return max(accumulate({'(': 1, ')': -1}[ch] for ch in s if ch in '()'), default = 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans = cur = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                cur += 1\n",
    "                ans = max(cur, ans)\n",
    "            elif c == ')':\n",
    "                cur -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        if True:\n",
    "            s_stack = []\n",
    "            max_dep = 0\n",
    "            for c in s:\n",
    "                if c in \"(\": s_stack.append(c)\n",
    "                if c in \")\": \n",
    "                    max_dep = max(max_dep, len(s_stack))\n",
    "                    s_stack.pop()\n",
    "            return max_dep\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        else:\n",
    "            s_stack = []\n",
    "            max_dep = 0\n",
    "            for c in s:\n",
    "                if c in [\"(\"]:\n",
    "                    s_stack.append(\"C\")\n",
    "                    max_dep = max(max_dep, len(s_stack))\n",
    "                elif c in [\")\"]:\n",
    "                    s_stack.pop()\n",
    "            return max_dep\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        list1 = []\n",
    "        res = 0\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                list1.append(i)\n",
    "                res = max(res,len(list1))\n",
    "            elif i == ')':\n",
    "                list1.pop()\n",
    "        return(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxDepth(self, s: str) -> int:\r\n",
    "        current_depth = 0\r\n",
    "        max_depth = 0\r\n",
    "\r\n",
    "        for char in s:\r\n",
    "            if char == '(':\r\n",
    "                current_depth += 1\r\n",
    "                max_depth = max(max_depth, current_depth)\r\n",
    "            elif char == ')':\r\n",
    "                current_depth -= 1\r\n",
    "\r\n",
    "        return max_depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans,size=0,0\n",
    "        for i in s:\n",
    "            if i=='(':\n",
    "                size+=1\n",
    "                ans=max(ans,size)\n",
    "            if i==')':\n",
    "                size-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        count = 0\n",
    "        tmp_max = 0\n",
    "        for char in s:\n",
    "            if char == \"(\":\n",
    "                count += 1\n",
    "                if count > tmp_max:\n",
    "                    tmp_max = count\n",
    "            if char == \")\":\n",
    "                count -= 1\n",
    "        return tmp_max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        stack = list()\n",
    "        ans = 0\n",
    "        for ch in s:\n",
    "            if ch == \")\" and stack[-1] == \"(\":  # 题目保证了右括号出现时左括号必有，不然还得判断stack\n",
    "                stack.pop()\n",
    "            elif ch == \"(\":\n",
    "                stack.append(ch)\n",
    "            ans = max(ans,len(stack))\n",
    "        return ans\n",
    "\n",
    "        #遍历写法\n",
    "        # ans, size = 0, 0\n",
    "        # for ch in s:\n",
    "        #     if ch == '(':\n",
    "        #         size += 1\n",
    "        #         ans = max(ans, size)\n",
    "        #     elif ch == ')':\n",
    "        #         size -= 1\n",
    "        # return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        cur,ans = 0 , 0\n",
    "        for c in s:\n",
    "            if c == \"(\":\n",
    "                cur += 1\n",
    "            elif c == ')':\n",
    "                cur -= 1\n",
    "            ans = max(ans,cur)\n",
    "        return ans\n",
    "\n",
    "# 核心思路其实就是统计最大的连续左括号的数量。\n",
    "# 遍历整个字符串，遇到左括号，总数+1，遇到右括号总数-1。\n",
    "# 实时更新最大连续左括号的数量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        # list1 = [str(i) for i in range(10)] + ['+','-','/']\n",
    "        # temp = []\n",
    "        count = 0\n",
    "        depth = 0\n",
    "        for item in s:\n",
    "            if item == '(':\n",
    "                count += 1\n",
    "                depth = max(depth,count)\n",
    "            elif item == ')':\n",
    "                count -= 1\n",
    "            # if item in list1:\n",
    "            #     temp.append(count)\n",
    "        \n",
    "        return depth\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        res = 0\n",
    "        d =0\n",
    "        for c in s:\n",
    "            if c == \"(\":\n",
    "                d += 1\n",
    "            if c == \")\":\n",
    "                d -= 1\n",
    "            res = max(res,d)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "\n",
    "        s1 = ''\n",
    "        for i in s:\n",
    "            if i == '(' or i == ')':\n",
    "                s1 += i\n",
    "\n",
    "        count = 0\n",
    "        while '()' in s1:\n",
    "            s1 = s1.replace('()', '', s1.count('()'))\n",
    "            count += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        result = 0\n",
    "        left_num = 0\n",
    "        for each in s:\n",
    "            if each == '(':\n",
    "                left_num += 1\n",
    "                result = max(result, left_num)\n",
    "            elif each == ')':\n",
    "                left_num -= 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        i = 0\n",
    "        res = [0]\n",
    "        for char in s:\n",
    "            if char == '(':\n",
    "                i += 1\n",
    "                res.append(i)\n",
    "            elif char == ')':\n",
    "                i -= 1\n",
    "                res.append(i)\n",
    "        return max(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        max_=0\n",
    "        in_=0\n",
    "        for i in s:\n",
    "            if i=='(':\n",
    "                in_+=1\n",
    "            elif i==')':\n",
    "                in_-=1\n",
    "            max_=max(in_,max_)\n",
    "        return max_\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        i = 0\n",
    "        ret = []\n",
    "        for t in s:\n",
    "            if t == '(':\n",
    "                i += 1\n",
    "            elif t == ')':\n",
    "                i -= 1\n",
    "            else:\n",
    "                continue\n",
    "            ret.append(i)\n",
    "        if ret:\n",
    "            return max(ret)\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        stack = 0\n",
    "        ans = 0\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                stack += 1\n",
    "                ans = max(ans,stack)\n",
    "            elif i == ')':\n",
    "                stack -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        re=[]\n",
    "        ns=[]\n",
    "        n=0\n",
    "        for l in s:\n",
    "            if l=='(':\n",
    "                re.append(l)\n",
    "                n=n+1\n",
    "                ns.append(n)\n",
    "            elif l==')':\n",
    "                re.pop(len(re)-1)\n",
    "                n=n-1\n",
    "        if len(ns)==0:        \n",
    "            return 0\n",
    "        return max(ns)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans, cur = 0, 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                cur += 1\n",
    "            elif c == ')':\n",
    "                cur -= 1\n",
    "            ans = max(ans,cur)\n",
    "        return ans\n",
    "\n",
    "\n",
    "# 核心思路其实就是统计最大的连续左括号的数量。\n",
    "# 遍历整个字符串，遇到左括号，总数+1，遇到右括号总数-1。\n",
    "# 实时更新最大连续左括号的数量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        list1 = []\n",
    "        max_length = 0\n",
    "        for item in s:\n",
    "            if item == '(':\n",
    "                list1.append(item)\n",
    "            if item == ')':\n",
    "                list1.pop()\n",
    "            if len(list1) > max_length:\n",
    "                max_length = len(list1)\n",
    "            \n",
    "        return max_length\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        cur=ms=0\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                cur+=1\n",
    "                ms=max(cur,ms)\n",
    "            elif i ==')':\n",
    "                cur-=1\n",
    "        return ms"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        count = 0\n",
    "        arr = []\n",
    "        for i in s:\n",
    "            if i == \"(\":\n",
    "                count += 1\n",
    "                arr.append(count)\n",
    "            elif i == \")\":\n",
    "                count -= 1\n",
    "                arr.append(count)\n",
    "        if not arr:\n",
    "            return 0\n",
    "        return max(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans=0\n",
    "        now=0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                now+=1\n",
    "                ans=max(ans,now)\n",
    "            elif c==')':\n",
    "                now-=1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        stack = []\n",
    "        res = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                stack.append(c)\n",
    "                res = max(len(stack), res)\n",
    "            if c == ')':\n",
    "                stack.pop()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans = cur = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                cur += 1\n",
    "                ans = max(cur,ans)\n",
    "            elif c == ')':\n",
    "                cur -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans,cur = 0,0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                cur += 1\n",
    "            elif c == ')':\n",
    "                cur -= 1\n",
    "            ans = max(ans,cur)    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        num = 0\n",
    "        all = 0\n",
    "        cishu = 0\n",
    "        kuohao = int(s.count(\"(\"))\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \"(\":\n",
    "                num +=1\n",
    "                cishu +=1\n",
    "                all = max(num,all)\n",
    "                if cishu == kuohao:\n",
    "                    return all\n",
    "                \n",
    "            elif s[i] == \")\":\n",
    "                num -=1\n",
    "        return (all)\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        stack = []\n",
    "        depth = 0\n",
    "        for i in range(len(s)):\n",
    "            char = s[i]\n",
    "            if char == '(':\n",
    "                stack.append(')')\n",
    "                depth = max(len(stack), depth)\n",
    "            elif char == ')':\n",
    "                stack.remove(stack[-1])\n",
    "        return depth\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        i = 0\n",
    "        ret = []\n",
    "        for s1 in s:\n",
    "            if s1 == '(':\n",
    "                i += 1\n",
    "            elif s1 == ')':\n",
    "                i -= 1\n",
    "            else:\n",
    "                pass\n",
    "            ret.append(i)\n",
    "        return max(ret)\n",
    "        # max_depth = depth = 0\n",
    "        # for t in s:\n",
    "        #     if t == '(':\n",
    "        #         depth += 1\n",
    "        #     elif t == ')':\n",
    "        #         depth -= 1\n",
    "        #     max_depth = max_depth if max_depth >= depth else depth\n",
    "        # return max_depth\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans, cur = 0, 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                cur += 1\n",
    "            elif c == ')':\n",
    "                cur -= 1\n",
    "            ans = max(ans,cur)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        #def 递归\n",
    "        ans = cur = 0\n",
    "        for c in s:\n",
    "            if c == '(': \n",
    "                cur += 1\n",
    "                ans = max(cur,ans)\n",
    "            elif c == ')':\n",
    "                cur -= 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans, cur = 0,0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                cur += 1\n",
    "            elif c == ')':\n",
    "                cur -= 1\n",
    "            ans = max(ans,cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans = 0 \n",
    "        left = 0 \n",
    "        for ch in s :\n",
    "            if ch == '(' :\n",
    "                left+=1\n",
    "                ans = max(ans , left)\n",
    "            elif ch == ')' :\n",
    "                left -= 1\n",
    "        return ans \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans, cur = 0, 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                cur += 1\n",
    "            elif c == ')':\n",
    "                cur -= 1\n",
    "            ans = max(ans,cur)\n",
    "        return ans  \n",
    "\n",
    "\n",
    "# 核心思路其实就是统计最大的连续左括号的数量。\n",
    "# 遍历整个字符串，遇到左括号，总数+1，遇到右括号总数-1。\n",
    "# 实时更新最大连续左括号的数量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans, depth = 0, 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                depth += 1\n",
    "                ans = max(ans, depth)\n",
    "            elif c == ')':\n",
    "                depth -= 1\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        left=0\n",
    "        right=0\n",
    "        maxv=0\n",
    "        for i in s:\n",
    "            if i=='(':\n",
    "                left+=1\n",
    "            elif i==')':\n",
    "                maxv=max(maxv,left-right)\n",
    "                right+=1\n",
    "        return maxv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans, cur = 0,0\n",
    "        for c in s:\n",
    "            if c == \"(\":\n",
    "                cur += 1\n",
    "                ans = max(ans,cur)\n",
    "            elif c == \")\":\n",
    "                cur -= 1\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        # ls = []\n",
    "        # max_len = 0\n",
    "        # for i in s:\n",
    "        #     if len(ls) > max_len:\n",
    "        #         max_len = len(ls)\n",
    "        #     if i == '(':\n",
    "        #         ls.append(')')\n",
    "        #     elif not ls:\n",
    "        #         continue\n",
    "        #     #     ls.append(i)\n",
    "        #     elif i == ls[-1]:\n",
    "        #         ls.pop()\n",
    "        # print(max_len)\n",
    "        # return max_len\n",
    "\n",
    "\n",
    "        # ans = cur = 0\n",
    "        # for c in s:\n",
    "        #     if c == '(':\n",
    "        #         cur += 1\n",
    "        #         ans = max(cur, ans)\n",
    "        #     elif c == ')':\n",
    "        #         cur -= 1\n",
    "        # return ans\n",
    "\n",
    "        \n",
    "        max_len = 0\n",
    "        cur_len = 0\n",
    "        for i in s:\n",
    "            if i == '(':\n",
    "                cur_len += 1\n",
    "                max_len = max(max_len, cur_len)\n",
    "            elif i == ')':\n",
    "                cur_len -= 1\n",
    "                \n",
    "        print(max_len)\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        ans, cur = 0, 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                cur += 1\n",
    "            elif c == ')':\n",
    "                cur -= 1\n",
    "            ans = max(ans,cur)\n",
    "        return ans \n",
    "\n",
    "\n",
    "# 核心思路其实就是统计最大的连续左括号的数量。\n",
    "# 遍历整个字符串，遇到左括号，总数+1，遇到右括号总数-1。\n",
    "# 实时更新最大连续左括号的数量"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        st=''\n",
    "        m=0\n",
    "        n=0\n",
    "        for i in s:\n",
    "            if i not in ['(',')']:\n",
    "                continue\n",
    "            if i=='(':\n",
    "                if n>0:\n",
    "                    n-=1\n",
    "                else:\n",
    "                    m+=1\n",
    "            else:\n",
    "                n+=1\n",
    "        return m\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        count = 0\n",
    "        max_count = 0\n",
    "        for a in s:\n",
    "            if a == '(':\n",
    "                count += 1\n",
    "            elif a == ')':\n",
    "                count -= 1\n",
    "            max_count = max(max_count,count)\n",
    "        return max_count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, s: str) -> int:\n",
    "        stack, cnt = 0, 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                stack += 1\n",
    "                cnt = max(cnt, stack)\n",
    "            elif c == ')':\n",
    "                stack -= 1\n",
    "        return cnt  \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
